#include <stdio.h>
#include <math.h>
#include <stdlib.h>
// 解决0-1背包问题的算法
int bag(int n, int c, int w[], int v[]);
// 主函数
int main()
{
  int i, num, maxv = 0;
  // 商品数量n,背包容量c
  int n, c, *w, *v, tempw, tempv;
  printf("请输入商品的数量和背包的容量:");
  scanf("%d%d", &n, &c);
  w = calloc(n, sizeof(int));
  v = calloc(n, sizeof(int));
  // 输入重量
  printf("input the weights:");
  for (i = 0; i < n; i++)
    scanf("%d", &w[i]);
  // 输入价值
  printf("input the values:");
  for (i = 0; i < n; i++)
    scanf("%d", &v[i]);
  maxv = bag(n, c, w, v);
  printf("\nthe max value is %d", maxv);
}

// 解决0-1背包问题的算法
int bag(int n, int c, int *w, int *v)
{
  int i, k, tempw, tempv, maxv = 0;
  for (i = 0; i < pow(2, n); i++)
  { // 解空间
    k = i;
    tempv = tempw = 0;
    printf("\nsolution:i=%d\n", i + 1);
    printf("二进制表示：");
    for (int j = 0; j < n; j++)
    { // 相对应的每一个物品是否放入背包中
      int m = 0;
      if (k % 2 == 1)
      {
        tempv += v[j];
        tempw += w[j];
        m = 1;
      }
      printf("%d", m);
      k = k / 2;// 二进制移位，十进制和二进制转换规则
    }
    printf("  (total weight:%d,total value:%d)", tempw, tempv);
    if (tempw <= c)
    {
      if (tempv > maxv)
        maxv = tempv;
    }
  }
  return maxv;
}